#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ROW 5
#define COLUMN 5

typedef struct block
{
    int x; //行
    int y; //列
    int status;
    struct block *next;
} BLOCK;
// status意义：0表示孤立点或连通区域起点，其他数字表示与此点与多少个已有连通区域相连
//            若大于一，则需合并
BLOCK *Unit[4][ROW * COLUMN];

typedef struct node
{
    int color;
    int level;
} NODE;
NODE a[ROW][COLUMN];

void printArray()
{
    int i, j;
    for (i = 0; i < ROW; i++)
    {
        printf("+-------+-------+-------+-------+-------+\n");
        printf("|       |       |       |       |       |\n");
        for (j = 0; j < COLUMN; j++)
        {
            printf("|   ");
            switch (a[i][j].color)
            {
            case 0:
                printf("\33[31m%-2d\33[0m", a[i][j].level);
                break;
            case 1:
                printf("\33[32m%-2d\33[0m", a[i][j].level);
                break;
            case 2:
                printf("\33[33m%-2d\33[0m", a[i][j].level);
                break;
            case 3:
                printf("\33[34m%-2d\33[0m", a[i][j].level);
                break;
            default:;
            }
            printf("  ");
        }
        printf("|\n");
        printf("|       |       |       |       |       |\n");
    }
    printf("+-------+-------+-------+-------+-------+\n");
}

int connect(int x1, int y1, int x2, int y2) //判断两点是否连通
{
    if (x1 == x2)
    {
        if (((y1 + 1 == y2) && (y1 + 2 <= COLUMN)) || ((y1 - 1 == y2) && (y1 - 1 >= 0)))
            return 1;
        else
            return 0;
    }
    if (y1 == y2)
    {
        if (((x1 + 1 == x2) && (x1 + 2 <= ROW)) || ((x1 - 1 == x2) && (x1 - 1 >= 0)))
            return 1;
        else
            return 0;
    }
    return 0;
}

void Append(BLOCK *L, int x, int y, int status) //在链表L最后插入元素
{
    BLOCK *p = L;
    while (p->next)
    {
        p = p->next;
    }
    BLOCK *new_block;
    new_block = (BLOCK *)malloc(sizeof(BLOCK)); //插入新节点
    new_block->x = x;
    new_block->y = y;
    new_block->status = status;
    new_block->next = NULL;
    p->next = new_block;
}

void judge_connect(int x, int y)
{
    int status = 0; //是否已有连通块
    BLOCK *p;
    int i;
    for (i = 0; i < ROW * COLUMN && Unit[a[x][y].color][i]->next; i++)
    {
        p = Unit[a[x][y].color][i];
        p = p->next;
        while (p)
        {
            if (connect(x, y, p->x, p->y))
            {
                status++;
                Append(Unit[a[x][y].color][i], x, y, status);
            }
            p = p->next;
        }
    }
    if (status == 0)
    {
        Append(Unit[a[x][y].color][i], x, y, status);
        i++;
    }
}

void combine(BLOCK *L1, BLOCK *L2)
{
    BLOCK *p = L1;
    BLOCK *q = L2->next;
    while (p->next)
    {
        p = p->next;
    }
    p->next = q;
    L2->next = NULL;
}

void initial_unit()
{
    int i, j;
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < ROW * COLUMN; j++)
        {
            Unit[i][j] = (BLOCK *)malloc(sizeof(BLOCK));
            Unit[i][j]->x = 0;
            Unit[i][j]->y = 0;
            Unit[i][j]->status = 0;
            Unit[i][j]->next = NULL;
        }
    }
}

void free_unit()
{
    int i, j;
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < ROW * COLUMN; j++)
        {
            free(Unit[i][j]);
        }
    }
}

void find_connect(int times)
{
    int i, j;
    if (times != 0) //如果不是第一次
    {
        free_unit();
        initial_unit();
    }
    for (i = 0; i < ROW; i++)
    {
        for (j = 0; j < COLUMN; j++)
        {
            judge_connect(i, j);
        }
    }
    BLOCK *p, *q;
    for (int k = 0; k < 4; k++) //去重
    {
        for (i = 0; i < ROW * COLUMN && Unit[k][i]->next; i++)
        {
            p = Unit[k][i]->next;
            while (p)
            {
                if (p->status > 1)
                {
                    for (j = 0; j < i; j++)
                    {
                        q = Unit[k][j]->next;
                        while (q)
                        {
                            if (p->x == q->x && p->y == q->y && q->status <= 1)
                            {
                                combine(Unit[k][i], Unit[k][j]);
                            }
                            q = q->next;
                        }
                    }
                }
                p = p->next;
            }
        }
    }
}

int length(BLOCK *L)
{
    BLOCK *p = L;
    int length = 0;
    p = p->next;
    while (p)
    {
        p = p->next;
        length++;
    }
    return length;
}

int exist_connect() //若所有unit长度均为1，判定为无连通，游戏结束
{
    int i, j;
    int result = 0;
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < ROW * COLUMN; j++)
        {
            if (length(Unit[i][j]) >= 2)
                result++;
        }
    }
    return result;
}

void walk(BLOCK *L) //打印
{
    BLOCK *p = L;
    p = p->next;
    if (length(L) >= 2)
    {
        while (p)
        {
            if (p->status <= 1)
            {
                printf("(%d,%d) ", p->x + 1, p->y + 1);
            }
            p = p->next;
        }
        printf("\n");
    }
}

//合并相同颜色块
void merge(BLOCK *L, int x, int y)
{
    BLOCK *p = L;
    p = p->next;
    int sum = 0;
    while (p)
    {
        sum += a[p->x][p->y].level;
        a[p->x][p->y].level = 0;
        p = p->next;
    }
    a[x - 1][y - 1].level = sum;
}

//掉落
void drop()
{
    int i, j;
    int k;
    for (j = 0; j < 5; j++)
    {
        k = 4;
        for (i = 4; i >= 0; i--)
        {
            if (a[i][j].level != 0)
            {
                a[k][j].level = a[i][j].level;
                a[k][j].color = a[i][j].color;
                if (k != i) 
                {
                    a[i][j].level = 0;
                    a[i][j].color = 0;
                }    
                k--;
            }
        }
    }
}

//补充
void complement()
{
    int i,j;
    srand((unsigned)time(NULL));
    for (i = 0; i < ROW; i++)
    {
        for (j = 0; j < COLUMN; j++)
        {
            if (a[i][j].level == 0)
            {
                a[i][j].color = rand() % 4;
                a[i][j].level = rand() % 3 + 1;
            }
        }
    }
}

int main()
{
    int i, j;
    int color;
    int x, y;
    int num;
    int times = 0;
    srand((unsigned)time(NULL));
    for (i = 0; i < ROW; i++)
    {
        for (j = 0; j < COLUMN; j++)
        {
            a[i][j].color = rand() % 4;
            a[i][j].level = rand() % 3 + 1; //初始自然生成1，2，3级
        }
    }
    initial_unit();                       //初始化unit
    while (exist_connect() || times == 0) //首次执行或存在连通块时，可以循环
    {
        printArray();        //显示原数组
        find_connect(times); //构造unit
        if(!exist_connect())
        {
            break;
        }
        printf("输入要合并的颜色(1->红,2->绿,3->黄,4->蓝)\n");
        scanf("%d", &color);
        for (j = 0; j < ROW * COLUMN; j++)
        {
            if (length(Unit[color - 1][j]) >= 2)
            {
                printf("区域%d:", j);
                walk(Unit[color - 1][j]);
            }
        }
        printf("-----------------------\n");
        printf("输入要合并的区域编号\n");
        scanf("%d", &num);
        if (length(Unit[color - 1][num]) < 2)
            printf("此位置无法合并！\n");
        else
        {
            printf("输入要合并的目标位置(x,y)\n");
            printf("x:");
            scanf("%d", &x);
            printf("y:");
            scanf("%d", &y);
            merge(Unit[color - 1][num], x, y); //将此unit合并到(x,y)位置
        }
        drop();       //掉落
        complement(); //空位补充（随机颜色1～4、随机级别1～3）
        times++;
    }
    printf("-----------------------------------------------\n");
    printf(" 我【冯浩】代表【唐山艾唐元®巴氏鲜奶】恭喜您:         \n");
    printf("                                               \n");
    printf("               无 路 可 走 了！                  \n");
    printf("                                               \n");
    printf("                       联系电话:13832928851 冯浩 \n");
    printf("-----------------------------------------------\n");
    return 0;
}

